package leetCode;

public class AddTwoNumbers {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode r1 = reverse(l1);
//        ListNode r2 = reverse(l2);
//        System.out.print("reversed");
        ListNode res = getRes(l1, l2);
        return (res);
    }

    private ListNode getRes(ListNode r1, ListNode r2) {
        boolean add = false;
        ListNode p = r1, q = r2;
        ListNode ret = null;
        ListNode cur = null;
        ListNode prev = null;
        while (p != null && q != null) {
            int res = p.val + q.val;
            if (add) {
                res++;
            }
            add = false;
            if (res > 9) {
                res %= 10;
                add = true;
            }
            cur = new ListNode(res);
            if (ret == null) {
                ret = cur;
            } else {
                prev.next = cur;
            }
            prev = cur;
            p = p.next;
            q = q.next;
        }
        ListNode remaining = p == null ? q : p;
        while (add) {
            add = false;
            int res = remaining != null ? remaining.val : 0;
            res++;
            if (res > 9) {
                res %= 10;
                add = true;
            }
            cur = new ListNode(res);
            prev.next = cur;
            prev = cur;
            if (remaining != null)
                remaining = remaining.next;
        }
        //娉ㄦ剰5+5=10杩欑瓒呭嚭鏈�楂樹綅鐨勬儏鍐�
        prev.next = remaining;
        return ret;
    }

    private ListNode reverse(ListNode l1) {
        ListNode cur = l1;
        ListNode nxt = cur.next;
        cur.next = null;
        while (nxt != null) {
            ListNode nnext = nxt.next;
            nxt.next = cur;
            cur = nxt;
            nxt = nnext;
        }
        return cur;
    }

    public static void main(String[] args) {

    }
}
